package com.waiting.leetcode;

import java.util.Stack;

/**
 * @Description
 * @Author bjweitingting
 * @Date 2019/3/7
 **/
public class ReverseLinkedListII92 {
    public static void main(String[] args) {
        ListNode x1 = new ListNode(1);
        ListNode x2 = new ListNode(2);
        ListNode x3 = new ListNode(3);
        ListNode x4 = new ListNode(4);
        ListNode x5 = new ListNode(5);
        x1.next = x2;
//        x2.next = x3;
//        x3.next = x4;
//        x4.next = x5;
        reverseBetween2(x1, 1, 2);
        while (x1 != null) {
            System.out.println(x1.val);
            x1 = x1.next;
        }
    }

    public static ListNode reverseBetween2(ListNode head, int m, int n) {
        Stack<ListNode> tmp = new Stack<>();
        ListNode mNode = head;
        int i = 1;
        for (; i < m; i++) {
            mNode = mNode.next;
        }
        ListNode index = mNode;
        for (; i <= n; i++) {
            tmp.push(index);
            index = index.next;
        }
        for (i = m; i <= (m + n) / 2; i++) {
            int x = mNode.val;
            ListNode y = tmp.pop();
            mNode.val = y.val;
            y.val = x;
            mNode = mNode.next;
        }
        return head;
    }


    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null)
            return null;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode preNode = dummy;
        int i = 1;
        while (preNode.next != null && i < m) {
            preNode = preNode.next;
            i++;
        }
        if (i < m)
            return head;
        ListNode mNode = preNode.next;
        ListNode cur = mNode.next;
        while (cur != null && i < n) {
            ListNode next = cur.next;
            cur.next = preNode.next;
            preNode.next = cur;
            mNode.next = next;
            cur = next;
            i++;
        }
        return dummy.next;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}